package com.example.nirvana.dataStructure;

/**
 * 前缀树
 */
public class TrieTree {
    private Node root;

    public void insert(String word) {
        if (null == word) {
            return;
        }

        char[] chars = word.toCharArray();
        Node node = root;

        for (int i = 0; i < chars.length; i++) {
            node.pass++;

            int path = chars[i] - 'a';

            if (node.nexts[path] == null) {
                node.nexts[path] = new Node();
            }

            node = node.nexts[path];
            node.pass++;
        }
        node.end++;
    }

    /**
     * 指定字符串出现次数
     *
     * @param word 字符串出
     * @return 出现次数
     */
    public int search(String word) {
        if (null == word) {
            return 0;
        }

        Node node = root;

        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                return 0;
            }
            node = node.nexts[path];
        }
        return node.end;
    }

    /**
     * 指定前缀出现次数
     *
     * @param pre
     * @return
     */
    public int searchPre(String pre) {
        if (pre == null) return 0;
        Node node = root;
        char[] chars = pre.toCharArray();
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                return 0;
            }
            node = node.nexts[path];
        }
        return node.pass;
    }


    /**
     * 前缀树的删除
     *
     * @param word
     */
    public void delete(String word) {
        if (search(word) == 0)
            return;
        char[] chars = word.toCharArray();
        Node node = root;
        // 根节点 -1
        node.pass--;
        int path = 0;
        // 遍历字符串
        for (int i = 0; i < chars.length; i++) {
            // 计算路径偏移
            path = chars[i] - 'a';
            // 如果路径的尾节点 pass-1 后为 0，将这个尾节点置为 null，直接返回
            if (--node.nexts[path].pass == 0) {
                node.nexts[path] = null;
                return;
            }
            // 移动节点指针
            node = node.nexts[path];
        }
        // 遍历后沿途的 pass 都已经 -1，最后 end - 1
        node.end--;
    }

    class Node {
        int pass;
        int end;
        Node[] nexts;

        public Node() {
            pass = 0;
            end = 0;
            nexts = new Node[26];
        }
    }
}
